package cuiyt.datastructure.rbtree.bst;


import java.util.Comparator;

/**
 * @author cyt
 * @describe
 * @create 2020-12-17 20:20
 */
public class Bst<E> extends BinaryTree<E> {
    /**
     * 删除之后调整二叉搜索树
     *
     * @param node
     */
    protected void afterRemove(Node<E> node) {

    }

    /**
     * 添加之后调整二叉搜索树
     *
     * @param node
     */
    protected void afterAdd(Node<E> node) {

    }

    private Comparator<E> comparator;

    public Bst() {
        this(null);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        toString(rootNode, sb, "");
        return sb.toString();
    }

    private void toString(Node root, StringBuilder sb, String preFix) {
        if (root == null) {
            return;
        }
        sb.append(preFix).append(root.value).append("\n");
        toString(root.left, sb, preFix + "L");
        toString(root.right, sb, preFix + "R");
    }

    /**
     * 提供外部比较器
     *
     * @param comparator
     */
    public Bst(Comparator comparator) {
        this.comparator = comparator;
    }

    /**
     * 添加元素
     *
     * @param element
     */
    public void add(E element) {
        checkElement(element);
        /**
         * 添加根节点
         */
        if (rootNode == null) {
            rootNode = createNode(element, null);
            size++;
            afterAdd(rootNode);
            return;
        }
        /**
         * 添加 非根节点
         * 1、找到根节点
         * 2、对比左右子树，找到要插入的位置
         *
         * res 当前要插入位置的方向
         * parent 当前要插入节点的父节点
         *
         * */
        Node<E> node = rootNode;
        Node<E> parent = null;
        int res = 0;
        while (node != null) {
            res = compare(element, node.value);
            parent = node;
            if (res > 0) {
                node = node.right;
            } else if (res < 0) {
                node = node.left;
            } else {
                /**
                 * 相等直接就返回了
                 */
                node.value = element;
                return;
            }
        }
        Node<E> newNode = createNode(element, parent);
        /**
         * 找到父节点之后， 开始插入元素
         */
        if (res > 0) {
            parent.right = newNode;
        } else if (res < 0) {
            parent.left = newNode;
        }
        afterAdd(newNode);
        size++;
    }

    /**
     * 比较节点大小的函数
     *
     * @param e1
     * @param e2
     * @return
     */
    private int compare(E e1, E e2) {
        /**
         * 如果提供的有外部比较器就使用外部比较器
         * 没有的话， 就直接使用元素本身的比较策略来比较
         */
        if (comparator != null) {
            return comparator.compare(e1, e2);
        } else {
            /**
             * 强制转化为  Comparable 进行元素的比较
             */
            return ((Comparable<E>) e1).compareTo(e2);
        }
    }

    /**
     * 外部传递过来的只是一个元素， 我们在树中要找到这个节点
     * 然后删除节点
     *
     * @param element
     */
    public void remove(E element) {
        remove(node(element));
    }

    /**
     * 删除节点
     * 此时需要分析节点度的大小
     *
     * @param node
     */
    private void remove(Node node) {
        if (node == null) {
            return;
        }
        size--;
        /**
         * 先删除度为2 的节点
         * 然后在处理度为0 、 1 的节点
         */
        if (node.hasTwoChildren()) {
            /**
             * 1、找到后继节点
             * 2、后继节点替换 度为2 的节点值
             * 3、删除后继节点
             */
            Node s = successor(node);
            node.value = s.value;
            node = s;
        }
        // 开始处理 度为 0 、 1 的节点
        // replacement 为null的时候 是 度为 0
        Node replacement = node.left != null ? node.right : node.right;
        if (replacement != null) {
            // 度为1 的节点
            replacement.parent = node.parent;
            // 度为1 的节点 并且还是根节点
            if (node.parent == null) {
                rootNode = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else if (node == node.parent.right) {
                node.parent.right = replacement;
            }

            afterRemove(node);
        } else if (node.parent == null) {
            /**
             * 叶子节点， 并且还是 根节点
             */
            rootNode = null;
            afterRemove(node);
        } else {
            /**
             * 叶子节点
             */
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
            afterRemove(node);
        }
    }

    /**
     * 找到这个节点
     *
     * @param element
     * @return
     */
    public Node node(E element) {
        Node<E> node = rootNode;
        while (node != null) {
            int res = compare(element, node.value);
            if (res > 0) {
                node = node.right;
            } else if (res < 0) {
                node = node.left;
            } else {
                /**
                 * 相等直接就返回了
                 */
                return node;
            }
        }
        return null;
    }

    /**
     * 检查要插入的元素
     *
     * @param e
     */
    private void checkElement(E e) {
        if (e == null) {
            throw new IllegalArgumentException("element must is not null");
        }
    }
}
